package cn.xaut.贪心算法;

import java.util.Arrays;

public class demo455 {

    public int findContentChildren(int[] g, int[] s) {

        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int gi = 0, si = 0;
        while (si < s.length && gi < g.length) {
            if (s[si] >= g[gi]) {
                si ++;
                gi ++;
                count ++;
            } else 
                si ++;
        }

        return count;
    }

    // 逆向
    public int findContentChildren2(int[] g, int[] s) {

        Arrays.sort(g);
        Arrays.sort(s);
        
        int glen = g.length;
        int slen = s.length;
        
        int count = 0;
        int gi = glen - 1, si = slen - 1;
        while (gi >= 0 && si >= 0) {
            if (s[si] >= g[gi]) {
                si --;
                gi --;
                count ++;
            } else 
                gi --;
        }
        
        return count;
    }

    public static void main(String[] args) {

        System.out.println(new demo455().findContentChildren2(new int[]{1, 2, 3}, new int[]{1, 1}));//1
        System.out.println(new demo455().findContentChildren2(new int[]{1, 2}, new int[]{1, 2, 3}));//2
        System.out.println(new demo455().findContentChildren2(new int[]{10, 9, 8, 7}, new int[]{5, 6, 7, 8}));//2
    }
}
